package com.fanwei.afgorithm.code215;

/**
 * 数组中的第K个最大元素
 * 笔记：https://labuladong.gitbook.io/algo/mu-lu-ye-3/mu-lu-ye-3/kuai-su-xuan-ze
 * @author fanwei
 */
public class KthLargestElementInAnArray {

    public static void main(String[] args) {
        int[] arr = {3,2,1,5,6,4};
        int k =  2;
        System.out.println(findKthLargest(arr,k));
    }

    public static int findKthLargest(int[] nums, int k){
        int begin = 0, end = nums.length - 1;
        k = nums.length + 1 - k;
        while (begin < end){
            int pos = partition(nums,begin,end);
            if(pos == k-1) break;
            else if (pos < k-1) begin=pos + 1;
            else end = pos-1;
        }
        return nums[k-1];
    }

    private static int partition(int[]nums,int l,int r) {
        int less=l-1;//小于区的下标
        int  more=r;//大于区的下标，默认以最后一个下标的数作为划分值
        while(l<more){
            if(nums[l]<nums[r])
                swap(nums,++less,l++);
            else if  (nums[l]>nums[r])
                swap(nums,--more,l);
            else l++;
        }
        swap(nums,more,r);
        return less+1;//小于区位置+1可以得到划分的这个数的下标
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
